#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
struct segment_tree{
	int ti[N<<2];
	int mi[N<<2];
	int micnt[N<<2];
	// int hmi[N<<2]; must be 0
	int hmitot[N<<2];
	int atag[N<<2];
	int ataghmi[N<<2];
	int ataghmilen[N<<2];
	long long su[N<<2];
	void add(int now,int v,int ti){

	}
	void merge_mi(int &mi,int &cnt,int lmi,int lcnt,int rmi,int rcnt){
		if(lmi == rmi){
			mi = lmi;
			cnt = lcnt + rcnt;
		}else if(lmi < rmi){
			mi = lmi;
			cnt = lcnt + rcnt;
		}else{
			mi = rmi;
			cnt = lcnt + rcnt;
		}
	}
	void push_up(int now){
		ti[now] = max(ti[now<<1],ti[now<<1|1]);
		merge_mi(mi[now],mcnt[now],mi[now<<1],mcnt[now<<1],mi[now<<1|1],mcnt[now<<1|1]);
		hmitot[now] = hmitot[now<<1] + hmitot[now<<1|1];
		if(ti[now] > ti[now<<1] && mi[now<<1] == 0){
			hmitot[now] += 1ll*(ti[now] - ti[now<<1])*mcnt[now<<1];
		}
		if(ti[now] > ti[now<<1] && mi[now<<1|1] == 0){
			hmitot[now] += 1ll*(ti[now] - ti[now<<1|1])*mcnt[now<<1];
		}
	}
	void push_down(int now){
		
	}
	void update(int now,int l,int r,int x,int y,int v,int ti){
		if(x <= l&& r <= y){

		}
		push_down(now);
		int mid = (l + r)/2;
		if(x <= mid){
			update(now<<1,l,mid,x,y);
		}
		if(mid < y){
			update(now<<1|1,mid+1,r,x,y);
		}
		push_up(now);
	}

}
int main(){
}